The present invention relates to a computer network having multiple users. Specifically, method and apparatus are described which permits parties to a session or conversation in a connectionless exchange on the network to authenticate the other parties' status as a valid user who possesses the name he/she claims.
In the communication protocols which permit two parties to communicate over a common communication network, various techniques are employed to authenticate parties to each other. These procedures for authenticating the parties to a proposed session over the network screen out any party which either does not have the status of a valid user, or who may have lost his status as a valid user, or is a valid user under a different name than the one he claims to be.
These systems typically employ the use of electronic keys, possession of which identifies a user/party as being a valid user/party. The lack of possession of such a key would indicate that the user is not the one he claims to be, and is denied communication with another user/party over the network. These keys are often manually installed at the party's/user's secure memory storage to initially authorize the party. Each party generally stores N-1 keys where N is the total number of parties with which it may need to communicate. At the system generation phase, all potential parties to a session have to be known and the key shared between pairs of parties has to be safely and securely stored at each party's location. These keys are maintained through a system of bookkeeping, which identifies that possession of the particular key is the test to show that this party is the one he claims to be, authorized to communicate with a specific second party. The key itself does not effectively identify a party except from the bookkeeping.
The total number of keys required per party, and the further requirement that there be a global knowledge of all possible parties to a communication is a disadvantage in these systems. In order to avoid these disadvantages, several proposals have been made in the past. One of these systems is a so-called public key system attributed to Diffie and Hellman. This system, although believed to be secure, has risks that, given sufficient mathematical execution time, the security of the system may in fact be compromised. Further, the system for generating a key is computationally intensive. The public key system is essentially an encryption system, wherein each party holds two keys, one a publicly-known encryption key designed by a given authority and listed in a common directory, and the other a private decryption key. This system is basically adverse to the desirability of limiting the number of keys which must be distributed to each party.
Another system which is identified as being proposed by Needham and Schroeder provides for a three-party system, wherein a server is one of the parties, and dynamically distributes common keys to each pair of parties. In this system, each party stores a single key which is shared with its connected server. To initiate a communication between the parties, the initiating party must go first to the server to obtain keys to be used by the pair. Although it achieves one objective of minimizing the number of keys in the system, and the number of keys needed to be stored in each of the party's locations, it requires extensive communication with its server, thus burdening the network and server.
The connectivity to a server is not always practical in light of the additional cost and burden to the network traffic, and the possibility of link failure in the network.
In a paper by Rolf Blom, published as part of the advances in cryptology Proceedings of Crypto 82, pages 231 et seq., a method to encrypt messages transmitted in the network was proposed by supplying a key of M bits. The derivation of such encryption keys included assigning a unique user number to the users of the networks, and then with the unique user number, permitting that user to calculate a key based on his/her unique number and the unique number of another using a polynomial function. Blom's technique employed the use of a shared secret polynomial. Each user knows its share, but none knows the whole secret. Thus, the user knowing only partial information respecting the original polynomial is capable of generating an evaluation of the polynomial, using information supplied by the other party. The resulting key is used to encrypt the messages to be sent to the other user/participant in the communication session.
At the same time, the other user also receives the polynomial evaluated for his unique number I. This will permit this other user to calculate a similar key which will be identical to the key evaluated by the first user. Thus, each side has a key for encrypting and decrypting a message.
This method of sharing by polynomials has been used in the literature for various purposes, none of which includes authentication.
The process of encrypting entire messages for sending across a common network may also involve more security than is actually necessary. Using the key to encrypt all messages creates a risky exposure of the key-overusage. Therefore, it would be desirable to provide a secure method of authentication which did not require complete encryption of all messages, but yet had a limited number of keys needed to be stored at each party's location.